package com.wkh.datastructure.deque;

import java.util.Iterator;

/**
 * 基于循环数组实现双端队列
 * @param <E>
 */
public class ArrayDeque1<E> implements Deque<E>,Iterable<E> {
    private int head;
    private int tail;
    private E[] array;

    public ArrayDeque1(int capacity) {
        this.array = (E[]) new Object[capacity+1];
    }

    /**
     * 从队头添加
     *
     * @param value
     */
    @Override
    public boolean offerFirst(E value) {
        if (isFull()){
            return false;
        }
        int dec = dec(head, array.length);
        head = dec;
        array[head] = value;
        return true;
    }

    /**
     * 从队尾添加
     *
     * @param value
     * @return
     */
    @Override
    public boolean offerLast(E value) {
        if (isFull()){
            return false;
        }
        int inc = inc(tail, array.length);
        tail = inc;
        array[tail-1] = value;
        return true;
    }

    /**
     * 从队头删除
     *
     * @return
     */
    @Override
    public E poolFirst() {
        if (isEmpty()){
            return null;
        }
        E value = array[head];
        array[head] = null;
        int inc = inc(head, array.length);
        head = inc;
        return value;
    }

    /**
     * 从队尾删除
     *
     * @return
     */
    @Override
    public E poolLast() {
        if (isEmpty()){
            return null;
        }
        E value = array[tail-1];
        int dec = dec(tail, array.length);
        tail = dec;
        array[tail] = null;
        return value;
    }

    /**
     * 查看队头元素
     *
     * @return
     */
    @Override
    public E peekFirst() {
        if (isEmpty()){
            return null;
        }
        return array[head];
    }

    /**
     * 查看队尾元素
     *
     * @return
     */
    @Override
    public E peekLast() {
        if (isEmpty()){
            return null;
        }
        return array[tail];
    }

    /**
     * 判断是否为空
     *
     * @return
     */
    @Override
    public boolean isEmpty() {
        return head == tail;
    }

    /**
     * 判断是否已满
     *
     * @return
     */
    @Override
    public boolean isFull() {
        if (tail>head){
            return tail-head == array.length-1;
        } else if (tail<head) {
            return head-tail == 1;
        }else {
            return false;
        }
    }

    /**
     * 尾指针的运算
     * @param i 尾指针
     * @param length 数组长度
     * @return 返回尾指针的运算结果
     */
    static int inc(int i,int length){
        if (i + 1>=length){
            return 0;
        }
        return i+1;
    }

    /**
     * 头指针的运算
     * @param i 头指针
     * @param length 数组长度
     * @return 返回头指针的运算结果
     */
    static int dec(int i,int length){
        if (i<=0){
            return length-1;
        }
        return i-1;
    }

    /**
     * Returns an iterator over elements of type {@code T}.
     *
     * @return an Iterator.
     */
    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            int p = head;
            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E value = array[p];
                p = inc(p,array.length);
                return value;
            }
        };
    }
}
